
c_ij = [
    [0,5,21,13,6,15,12,20],
    [5,0,16,18,7,12,19,17],
    [21,16,0,33,16,7,17,11],
    [13,18,33,0,17,26,16,29],
    [6,7,16,17,0,9,12,14],
    [15,12,7,26,9,0,10,5],
    [18,19,17,16,12,10,0,13],
    [20,17,11,29,14,5,13,0]
]
N = len(c_ij)
inf = 100000
#确定插入位置
def get_pos(visited,k,c_ij):
    delta = inf
    pos = [None,None]
    i,j = len(visited)-2,len(visited)-1
    #从后向前寻找插入点，保证delta相等时尽量向前插
    while j != 0:
        tem = c_ij[visited[i]][k] + c_ij[k][visited[j]] - c_ij[visited[i]][visited[j]]
        if tem <= delta :
            delta = tem
            pos = [i,j]
        i -= 1
        j -= 1
    return pos,delta

def NI(visited,waiting,current_len,c_ij):
    visited_NI = list(visited)
    leng = current_len
    waiting_NI = list(waiting)
    
    while waiting_NI:
        tem = inf
        ii = None
        k = None
        for j in waiting_NI:
            for i in visited_NI:
                if c_ij[i][j] < tem:
                    tem = c_ij[i][j]
                    k = j
                    ii = i
        if len(visited_NI) == 1:
            visited_NI.append(k)
            waiting_NI.remove(k)
            leng += c_ij[visited_NI[0]][k]
            leng += c_ij[k][visited_NI[0]]
            continue
        pos,delta = get_pos(visited_NI,k,c_ij)
        print(visited_NI)
        print(ii,k,pos)
        visited_NI.insert(pos[1],k)
        
        waiting_NI.remove(k)
        leng += delta
    
    
    return leng,visited_NI

def CI(visited,waiting,current_len,c_ij):
    visited_CI = list(visited)
    leng = current_len
    waiting_CI = list(waiting)
    
    while waiting_CI:
        if len(visited_CI) == 1:
            tem = inf
            k = None
            for j in waiting_CI:
                for i in visited_CI:
                 if c_ij[i][j] < tem:
                        tem = c_ij[i][j]
                        k = j
            visited_CI.append(k)
            waiting_CI.remove(k)
            leng += c_ij[visited_CI[0]][k]
            leng += c_ij[k][visited_CI[0]]
            continue
        #对waiting里每个元素执行get_pos,获取最小delta
        tem = inf
        k = None
        pos_CI = None
        for j in waiting_CI:
            pos,delta = get_pos(visited_CI,j,c_ij)
            if tem >= delta:
                tem = delta
                k = j
                pos_CI = pos
        print(visited_CI)
        print(k,pos)
        visited_CI.insert(pos_CI[1],k)
        
        waiting_CI.remove(k)
        leng += tem

    return leng,visited_CI


print("NI:")
print(NI([0],[1,2,3,4,5,6,7],0,c_ij))

# print(c_ij[5][7] + c_ij[7][1] - c_ij[5][1])
# print(c_ij[4][7] + c_ij[7][5] - c_ij[4][5])
print("CI:")
print(CI([0],[1,2,3,4,5,6,7],0,c_ij))